Title: TASK 1
Author: Zheko Petrov
Company: FMI

TASK 1.3. PATH FINDING

This problem is strongly related to Dijkstra’s shortest path algorithm. The following paragraphs assume knowledge of this algorithm, so in case you are not familiar with it we recommend reading about it before reading the paragraphs below.

1. Trivial Algorithm (Dijkstra)

The trivial solution to this problem is to retrieve the whole graph using the provided libraries and to run Dijkstra’s algorithm. As stated in the problem statement such an algorithm will be assigned 20 points (since in this case K = T).

2. Slightly Less Trivial Algorithm (Dijkstra)

One can optimize the Dijkstra implementation above by making sure that he/she never asks for information that is never used. This means that the program will invoke the getXYM and getAdj subroutines only when it needs the information provided by them. Also, the program will terminate as soon as a path to the destination is found, so that it will never ask for the neighbors of those crossroads, which are farther from S (the starting point), compared to F (the destination). Our implementation of this algorithm scores about 40 points on the test data.

3. Heuristics

We all know that Dijkstra’s algorithm is optimal for general graphs. However, this doesn’t hold for our problem. The reason is that we have additional information, besides the vertices and edges of the graph: we are given coordinates of the crossroads. This gives us a lower bound on the length of any path connecting two crossroads: the path can never be shorter than the distance between the two crossroads. Having this additional information means that we can perform better than Dijkstra’s algorithm.

One can employ a number of different heuristics on how to exploit the coordinates information in order to improve Dijkstra’s algorithm. One example is to form a rectangle or an ellipse around S and F and to ignore all crossroads outside the selected area. One thing to be careful about however, is not to leave possible shortest paths outside your scope. As mentioned in the problem statement, you will receive 0 points in case you report an answer without making sure that there is no shorter path. This means that if there is a crossroad X, which would give a shorter path in case X is connected directly to the destination, you will have to retrieve all of X’s neighbors’ coordinates (just to make sure that there is no path through X that beats your supposedly shortest path). Such kinds of heuristics are expected to receive about 60 points, since achieving K ≤ J is practically impossible without an optimal algorithm (more on the choice of J below).

4. Optimal Algorithm

In the above paragraph we mentioned that we have to check certain kind of crossroads (i.e., we have to retrieve information about their neighbors). The general idea behind the algorithm in this section is to check only those crossroads that we have to check. This will yield us an optimal algorithm that does not make even a single unnecessary call to the getXYM and getAdj subroutines. Here is an explanation how.

We compute the P-number of a crossroad X as the shortest possible path from S through X to F. Thus the P-number of X is equal to the shortest known path from S to X, plus the distance from X to F.

Initially, the P-number of every crossroad (except S) is Infinity, as there is no known path to any of these crossroads. The P-number of S is equal to the distance between S and F. Now, having this P-number definition we will construct an algorithm very similar to Dijkstra’s. We will divide the crossroads into two sets: processed and unprocessed. Initially all crossroads are in the unprocessed set. Then we will perform the same operation repeatedly:

We pick the unprocessed crossroad with the smallest P-number and then we process it. The processing consists of retrieving the coordinates of all of its neighbors and updating those neighbors. The updating of a neighbor Y is similar to the one in Dijkstra’s algorithm: we check whether going to Y through X would improve Y’s P-number. Since the distance between Y and F is constant, updating the P-number is equivalent to updating the shortest path to Y. That is why the criterion for updating the P-number of Y is identical to the one in Dijkstra’s algorithm (i.e., whether the path to Y through X is shorter than the previously known shortest path to Y).

After updating X’s neighbors we move X into the processed set. We repeat the same step until F becomes the unprocessed crossroad with the smallest P-number (exactly as in Dijkstra’s algorithm).

Now let’s prove the correctness and the optimality of this algorithm. The proof of correctness again resembles Dijkstra. When we update the P-number of Y (an unprocessed neighbor of X) through X, we always have P-number(Y) greater than or equal to P-number(X). The reason is that:
P-number(Y) = ShortestPath(X) + Distance(X, Y) + Distance(Y, F)
P-number(X) = ShortestPath(X) + Distance(Y, F)

Taking the difference of the above two always yields a non-negative number (the sum of any two sides of a triangle is not less than the third side). The just-proven fact tells us that we can never improve the P-number of a crossroad in the unprocessed set to a value smaller than the value of X (because X is chosen to be the one with the smallest P-value among all unprocessed crossroads). A corollary follows: We have found X’s true P-number, since we can never improve it. This means that when X becomes equal to F we have found the true P-number of F, which is equal to the shortest path from S to F. This means we are ready to report our answer with 100% confidence of its correctness. All crossroads that we had to process are already processed, as they had P-numbers smaller than F.

Proving the optimality of the algorithm is even easier. We processed only crossroads with P-numbers smaller than F. Each such crossroad is a crossroad that we had to process (because it could yield a shortest path to F). We haven’t processed any crossroads with P-numbers greater than the P-number of F, hence we did not do any needless processing. That is why this algorithm is optimal (i.e., it makes an optimal number of calls to the getXYM and getAdj subroutines).

5. Source code

Here is an implementation of the last algorithm, written in the C language. You can probably find other implementations of this algorithm on the Internet, if you search for A* (or “A Star”), as this is the most popular name of this algorithm.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "module.h"

#define MAXN 8192

long n;
long source, dest;
long known[MAXN];
long x[MAXN];
long y[MAXN];
long m[MAXN];
double dist[MAXN];
double p[MAXN];
long prev[MAXN];
long anses;
long ans[MAXN];

int main(void) {
  long i, j;
  long best;
  double most;
  double d;

  start(&n, &source, &dest);
  known[source] = 1;
  getXYM(source, &x[source], &y[source], &m[source]);
  known[dest] = 1;
  getXYM(dest, &x[dest], &y[dest], &m[dest]);
  p[source] = sqrt((x[dest]-x[source])*(x[dest]-x[source])+
(y[dest]-y[source])*(y[dest]-y[source]));
  p[dest] = dist[dest] = 2000000000;
  while (1) {
    best = 0;
    most = 2000000000;
    for (i=1; i<=n; i++) if (known[i]==1) {
      if (p[i]<most) {
        best = i;
        most = p[i];
      }
    }
    if (best==dest) break;
    for (i=1; i<=m[best]; i++) {
      j = getAdj(best);
      if (!known[j]) getXYM(j, &x[j], &y[j], &m[j]);
      d = dist[best] + sqrt((x[j]-x[best])*(x[j]-x[best])+
(y[j]-y[best])*(y[j]-y[best]));
      if (!known[j] || d<dist[j]) {
        known[j] = 1;
        dist[j] = d;
        p[j] = d + sqrt((x[dest]-x[j])*(x[dest]-x[j])+
(y[dest]-y[j])*(y[dest]-y[j]));
        prev[j] = best;
      }
    }
    known[best] = 2;
  }

  while (best != source) {
    ans[anses] = best;
    anses++;
    best = prev[best];
  }
  done(anses+1);
  report(source);
  for (i=anses-1; i>=0; i--) report(ans[i]);
  
  return 0;
}

6. Test Data

The test data is constructed from a map of a real city (to the best of our knowledge the city is somewhere in Germany). The table below shows the number of crossroads (N) and streets (M), as well as the highest class of roads included on the map (R, on a scale 1 to 10). 1 means that only highways are included, while 10 means that even the pedestrian alleys are there. The table also features the value of K (the number of calls to the two subroutines) of the Jury’s implementation of the optimal algorithm and the same value (D) for the optimized Dijkstra implementation. The last column is the cutoff J for a score of 10 points on the test case. The cutoff is computed by running the same algorithm with the only difference that it finds all shortest paths from S to F. This is done in order to eliminate the factor of luck  (i.e., now it doesn’t matter how the contestant resolves ties with unprocessed crossroads, which have equal P-numbers).

Test | N | M | R | T = N+M | D | K | J
01 | 8 | 12 | 10 | 20 | 15 | 13 | 14
02 | 23 | 40 | 10 | 63 | 36 | 28 | 29
03 | 2039 | 4552 | 10 | 6591 | 6487 | 2208 | 2209
04 | 5277 | 11810 | 6 | 17087 | 16139 | 12418 | 12419
05 | 6560 | 15229 | 10 | 21789 | 18979 | 7352 | 7353
06 | 138 | 122 | 1 | 260 | 29 | 19 | 19
07 | 639 | 870 | 3 | 1509 | 371 | 291 | 293
08 | 1829 | 3176 | 4 | 5005 | 1046 | 383 | 386
09 | 6140 | 13667 | 6 | 19807 | 15385 | 5269 | 5272
10 | 6856 | 15889 | 10 | 22745 | 21551 | 7652 | 7625